/**
 * @file   class.cpp
 * @author xingyifan <xingyifan@xingyifan-VirtualBox>
 * @date   Thu Oct 15 22:54:38 2020
 * 
 * @brief  all  the functions and class
 * 
 * 
 */

#include "class.h"

DATA::DATA() {}

DATA::~DATA() {}

//init DATA
int DATA::set(int _index, double _val) {
    index = _index;
    val = _val;

    return 0;
}

double DATA::get(int k) {
    if (k==0) {
	return index*1.0;
    } else {
        return val;
    }
}

// DATA, first index, last index
int quick_sort(std::vector<DATA> &_A, int p, int n, int check) {
    if (n>p) {
	int q = partition(_A, p, n, check);
	quick_sort(_A, p, q-1, check);
	quick_sort(_A, q+1, n, check);
    }

    return 0;
}

//divide
int partition(std::vector<DATA> &_A, int p, int n, int check) {
    // check==0 -> index
    // check==1 -> val
    int k;
    
    if (check==0) {
	k = 0;
    } else {
	k = 1;
    }
    
    if (n==p+1) {
	if (_A[p].get(k)>_A[n].get(k)) {
	    DATA tmp = _A[p];
	    _A[p] = _A[n];
	    _A[n] = tmp;
	}

	return p;
    }

    int left = p;
    int right = n;
    double val = _A[p].get(k);
    
    while (left!=right) {
	while (_A[right].get(k)>=val && left<right) {
	    right--;
	}
	while (_A[left].get(k)<=val && left<right) {
	    left++;
	}

	if (left<right) {
	    DATA tmp = _A[left];
	    _A[left] = _A[right];
	    _A[right] = tmp;
	    right--;
	}     
    }

    DATA tmp = _A[p];
    _A[p] = _A[left];
    _A[left] = tmp;
    
    return left;
}

// resort the result to be stable
int stable(std::vector<DATA> &_A, int n) {
    for (int i=1;i<n;i++) {
	int first = i - 1;
	while (i<n && _A[i].get(1)==_A[i-1].get(1)) {
	    i++;
	}
	quick_sort(_A, first, i-1, 0);
    }
    
    return 0;
}

// use it to start sort
int stable_quick_sort(std::vector<DATA> &_A) {
    int n = _A.size();
    quick_sort(_A, 0, n-1, 1);
    stable(_A, n);
    
    return 0;
}
